package practise.alogrithm.gotoSiliconValley.array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by xinlyu on 8/4/2014.
 */
public class FilterOutOverlapAfterInsert {
    private List<Range> ranges ;
    public FilterOutOverlapAfterInsert(List<Range> ranges){
        Collections.sort(ranges);
        this.ranges = ranges;
    }
    public List<Range> insert(Range range){
       int index=0;
        int start = Integer.MAX_VALUE,end=-1;
        List<Range> rangeList = new ArrayList<>();
        for(;index<ranges.size()&& ranges.get(index).getEnd()<range.getStart();index++){
            rangeList.add(ranges.get(index));
        }
        // note, we should just examine the condition ranges.get(index).getStart()<=range.getEnd()
        //but not as ranges.get(index).getEnd()>=range.getStart(), as if we examine this, we have to
        // examine the ranges.get(index).getStart()<=range.getEnd(), but inactually, the first is already
        // contained in the previous loops
        for(;index<ranges.size()&&ranges.get(index).getStart()<=range.getEnd();index++){
            start = Math.min(ranges.get(index).getStart(),range.getStart());
            end = Math.max(ranges.get(index).getEnd(),range.getEnd());
        }
        if(end!=-1){
            rangeList.add(new Range(start,end));
        }
        for(;index<ranges.size();index++){
            rangeList.add(ranges.get(index));
        }
        return rangeList;
    }



}

class Range implements Comparable<Range>{
    private Integer start ;
    private Integer end;

    Range(Integer start, Integer end) {
        this.setStart(start);
        this.setEnd(end);
    }

    @Override
    public int compareTo(Range o) {
        if(getStart() != o.getStart()){
            return getStart() - o.getStart();
        }
        else{
            return getEnd() - o.getEnd();
        }
    }

    public Integer getStart() {
        return start;
    }

    public void setStart(Integer start) {
        this.start = start;
    }

    public Integer getEnd() {
        return end;
    }

    public void setEnd(Integer end) {
        this.end = end;
    }
}
